In this work, stirred yogurt variations in which milk-fat was replaced by a complex coacervate (CC) made up by whey protein isolate/Lactobacillus plantarum (Lp)/k-carrageenan, and sucrose by stevia were prepared. Microstructure, rheology and sensory attributes of the yogurt variations were examined. Sucrose substitution (6 wt%) by stevia (0.02 wt%) in full-fat yogurt (2.6 wt%) and reduced-fat yogurt (1.3 wt%) produced more compact gel networks in which the presence of non-micellar material was observed between casein clusters. Viscoelastic moduli of the yogurt variations containing stevia were significantly higher than those of the yogurt variations containing sucrose. Incorporation of CC (1.3, 2.6 and 3.9 wt%) produced reduced-fat yogurt variations exhibiting a progressively more compact protein network, higher viscoelastic moduli and preference sensory scores comparable to those displayed by the full-fat yogurt made with sucrose. Yogurt variations incorporating CC exhibited high probiotic survivability (> 8.1 log cfu g-1) after 21 days of storage.